package data_structure.mooc;

/**
 * LinkedList defined by myself,complete the addition,deletion,modification,look-up operation
 * 0 based
 * Specially in every operation,the position of the operation can be anywhere in the list
 * the element is the node:Node
 * To make the code more brief,set the dummy head for the list
 * @param <E>
 */
public class LinkedList<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this (e, null);
        }

        public Node() {
            this (null, null);
        }

        public Node parseArr(E []arr){
            Node node=new Node (arr[0]);
            Node head=node;
            for(int i = 1; i < arr.length; i++){
                node.next=new Node(arr[i]);
                node=node.next;
            }
            return head;
        }

        @Override
        public String toString() {
            return e.toString ();
        }

    }

    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node (null, null);
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

//addition
    public void add(int index, E e) {
        if(index<0||index>size){
            throw new IllegalArgumentException ("Add failed,Illegal index.");
        }
        Node prev = dummyHead;

        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node node=new Node(e);
        node.next=prev.next;
        prev.next=node;
//        prev.next = new Node (e, prev.next);
        size++;
    }

    public void addLast(E e){
        add (size,e);
    }

    public void addFirst(E e) {
        add (0,e);
    }
    //get operation

    public E get(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Get failed,Illegal index.");
        }
        Node current=dummyHead.next;
        for(int i=0;i < index; i++){
            current=current.next;
        }
        return current.e;
    }

    public E getFirst(){
        return get (0);
    }

    public E getLast(){
        return get (size-1);
    }

    public boolean contains(E e){
        for(Node current = dummyHead.next; current != null; current = current.next){
            if(current.e.equals (e)){
                return true;
            }
        }
        return false;
    }

    //modification operation
    public void set(int index,E e){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Set failed,Illegal index.");
        }
        Node node=dummyHead.next;
       for(int i=0;i<index;i++){
           node=node.next;
       }
       node.e=e;
    }
    //remove operation
    public E remove(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException ("Remove failed,Illegal index.");
        }
        Node prev=dummyHead;
        for(int i = 0; i < index; i++){
            prev = prev.next;
        }
        Node delNode=prev.next;
        E delE=delNode.e;
        prev.next=delNode.next;
        size--;
        delNode.next=null;
        return delE;
    }

    public void remove(E e){

        Node prev=dummyHead;
        while(prev.next!=null&&!prev.next.e.equals (e)){
            prev = prev.next;
        }
        if(prev.next==null)return;
        else{
            Node delNode=prev.next;
            Node next=prev.next.next;
            prev.next = next;
            delNode.next = null;
        }

    }

    public E removeFirst(){
        return remove (0);
    }
    public E removeLast(){
        return remove (size-1);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("List:");
        Node current = dummyHead.next;
        while (current != null) {
            sb.append (current.e).append ("-->");
            current=current.next;
        }
        sb.append("NULL");
        return sb.toString ();
    }

    public static void main(String[] args) {

        LinkedList<Integer>list=new LinkedList<Integer> ();
        for (int i = 0; i < 10; i++) {
            list.addFirst (i);
        }
        list.remove (new Integer (9));
        System.out.println(list);
    }
}
